package Aula8;

import java.util.ArrayList;

public class CidadesImpl implements Cidades {
	
	private double[][] custos;
	private Vertice[] vertices;
	
	public CidadesImpl(){
		super();
	}
	
	private Vertice noKnownMin(){
		Vertice verticeMin = null;
		double menor = Double.POSITIVE_INFINITY;
		for(int i = 0; i < vertices.length; i++){
			if(!vertices[i].isKnown() && vertices[i].getDist() < menor){
				verticeMin = vertices[i];
				menor = verticeMin.getDist();
			}
		}
		return verticeMin;
	}
	
	private ArrayList<Vertice> adjacent(int vertice){
		ArrayList<Vertice> lista = new ArrayList<Vertice>();
		for(int i = 0; i < custos[vertice].length; i++){
			if(custos[vertice][i] != Double.POSITIVE_INFINITY){
				lista.add(vertices[i]);
			}
		}
		return lista;
	}
	
	private void dijkstra(int origem){
		//tratar pra origem invalida!
		if(custos == null){
			throw new RuntimeException("Grafo nao preenchido!");
		}
		
		for(int i = 0; i < vertices.length; i++){
			vertices[i] = new Vertice(i);
		}
		
		Vertice vertice = vertices[origem];
		ArrayList<Vertice> adjList;
		double custo;
		
		vertice.setDist(0.0);
		
		while(vertice != null){
			vertice.activeKnown();
			adjList = adjacent(vertice.getId());
			for(Vertice adj:adjList){
				if(!adj.isKnown()){
					custo = custos[vertice.getId()][adj.getId()];
					if(vertice.getDist() + custo < adj.getDist()){
						adj.setDist(vertice.getDist() + custo);
					}
				}
			}
			vertice = noKnownMin();
		}
				 
	}

	public double menorTempodeViagem(int origem, int destino,
			double velocidadeMedia) {
		dijkstra(origem);
		Vertice dist = vertices[destino];
		return (dist.getDist() / velocidadeMedia) * 60; 
	
	}

	public void preencherGrafo(double[][] matriz, int numeroCidades) {
		custos = matriz;
		vertices = new Vertice[matriz.length];
	}
	
	public static void main(String[] args) {
        Cidades g = new CidadesImpl();
        
        double [][]matriz = {{Double.POSITIVE_INFINITY,17.0,20.0},{Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY,20.0},{Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY}};
        int tamanhoMatriz = 3;
        g.preencherGrafo(matriz, tamanhoMatriz);
        
        System.out.println("O menor tempo entre cidades 0 e 2, a 100km por hora: " + g.menorTempodeViagem(2, 1, 100) + " minutos");
        
    }
}
